"""
Problem 66: https://projecteuler.net/problem=66

pell equation x^2 - D*y^2 = 1

when D <= 1000, find the max x
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/20
'''


from commonfuncs.pellEquation import solve
limit = 1000
SquaresDict = {n: n**2 for n in range(limit)}


def violenceSearch(D: int):
    '''
    x^2 - D*y^2 = 1
    return x,y

    >>> print(violenceSearch(5))
    (9, 4)
    >>> print(violenceSearch(20))
    (9, 2)
    >>> violenceSearch(61)
    for 61, x >= 1000, not find answer.
    '''

    if D == 0:
        return 1, 1

    if not isinstance(D, int) or D < 0:
        return False

    D_sqrt = D**0.5
    if int(D_sqrt) == D_sqrt:
        return 1, 0

    x = 1
    while True:
        y = 1
        while True:
            if y >= x/D_sqrt:
                break
            try:
                if SquaresDict[x] - D*SquaresDict[y] == 1:
                    # print(f'x^2-{D}y^2==1,({x},{y})')
                    return x, y
            except KeyError:
                print(
                    f'for {D}, x >= {limit}, not find answer.')
                return None

            y += 1
        x += 1


def solution(limit: int = 1000) -> int:
    '''
    >>> print(solution(7))
    9
    '''

    return max([solve(D)[0]
                for D in range(limit+1)])


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 16421658242965910275055840472270471049
    # violenceSearch() do not apply
